package com.clstu.search;

import java.util.Arrays;

/**
 * 研究斐波那契查找算法
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        //测试斐波那契数列
        System.out.println(Arrays.toString(getFibArr(20)));
        int[] arr = {0,1,2,3,4,5,6,7,8,9};
        System.out.println(fibSearch(arr,20));
    }

    //编写方法实现斐波那契查找(非递归版,因为要用到temp[]所以只能写个非递归版)
    public static int fibSearch(int[] arr,int findVal){
        //思路分析:
        //过程跟二分法一样,不过mid变成了fib(k)-1;代表的黄金分割点(0.618点)
        int left=0;
        int right = arr.length-1;
        int[] fibArr = getFibArr(20);
        int k=0;//分割点的k值
        //确定k为恰好大于数组长度的斐波那契数列的下标
        while (fibArr[k]-1<right){
            k++;
        }
        //扩充分割点的右边(扩充部分用最右边的数填充)(新的temp代替原数组,再temp种用黄金分割发查找)
        int[] temp = Arrays.copyOf(arr,fibArr[k]);
        for (int i = right+1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        //用黄金分割法查找(注意此时查找的时temp数列,不是arr!!!!!!)
        int mid = left+fibArr[k-1]-1;
        while (true){
            System.out.println("left = "+left+"  right = "+right+"  mid = "+mid);
            //如果找不到
            if(left>right){
                return -1;
            }
            //下面3种情况
            if(findVal>temp[mid]){
                left = mid+1;
                k-=2;
                mid = left+fibArr[k-1]-1;
            }else if(findVal<temp[mid]){
                right = mid-1;
                k--;
                mid = left+fibArr[k-1]-1;
            }else {
                return mid>right?right:mid;
            }
        }
    }


    //编写方法得到一个斐波那契数列
    public static int[] getFibArr(int n){
        //如果时前两项
        if(n==1) return new int[]{1};
        if(n==2) return new int[]{1,1};
        int[] fibArr = new int[n];
        fibArr[0]=1;
        fibArr[1]=1;
        for (int i = 2; i < n; i++) {
            fibArr[i] = fibArr[i-1]+fibArr[i-2];
        }
        return fibArr;
    }
}
